import java.util.ArrayList;
import java.util.List;

class Solution {
//     回溯
//     找到 以当前位置起始的 回文子串
//     加入到 list 之后, 再递归的位置就是 这个子串的下一个位置
//     递归的过程中需要用到 循环
    public List<List<String>> lists=new ArrayList<>();
    public List<String> list=new ArrayList<>();
    public String[][] partition(String s) {
        dfs(0, s.length(), s);
        String[][] ans=new String[lists.size()][];
        for(int i=0;i<lists.size();i++){
            List<String> temp=lists.get(i);
            ans[i]=new String[temp.size()];
            for(int j=0;j<ans[i].length;j++){
                ans[i][j]=temp.get(j);
            }
        }
        return ans;
    }

    // 深度优先遍历
    public void dfs(int index, int length, String s){
        if(index==length){
            lists.add(new ArrayList<>(list));
            return ;
        }
        for(int i=index+1;i<=length;i++){
            String substr=s.substring(index, i);
            if(!isReverse(substr)){
                continue;
            }
            list.add(substr);
            dfs(i, length, s);
            list.remove(list.size()-1);
        }
    }

    // 判断是否 回文
    public boolean isReverse(String str){
        int left=0;
        int right=str.length()-1;
        while(left<right){
            if(str.charAt(left)!=str.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}